/* Copyright (c) 2006 by M Aamir Maniar 
 * 
 * Permission is hereby granted, free of charge, to any person obtaining 
 * a copy of this software and associated documentation files (the 
 * "Software"), to deal in the Software without restriction, including 
 * without limitation the rights to use, copy, modify, merge, publish, 
 * distribute, sublicense, and/or sell copies of the Software, and to 
 * permit persons to whom the Software is furnished to do so, subject to 
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be 
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 * 
 * */

namespace Generic.DataStructures
{
	using System;
	using SysGeneric = System.Collections.Generic;
	using System.Text;
	using System.Diagnostics;
	using System.Runtime.InteropServices;

	/// <summary>
	/// Represetns the array based stack by implementing <see cref="Stack&lt;T&gt;"/>.
	/// </summary>
	/// <remarks>
	/// Use the stack when you want list based on FIFO (first-in last-out) principal.
	/// </remarks>
	/// <typeparam name="T"></typeparam>
	[
	DebuggerDisplay("Count = {Count}"),
	ComVisible(true),
	DebuggerTypeProxy(typeof(Generic.DataStructures.Stack<>.StackDebugView))
	]
	public class Stack<T> : IStack<T>
	{
		#region Initial Member Declaration
		public const int DEFAUT_CAPACITY = 1024;
		private T[] _array;
		private int _size;
		#endregion

		#region Constructors
		/// <summary>
		/// Initializes a new instance of the <see cref="Stack&lt;T&gt;"/> class.
		/// </summary>
		public Stack() : this(DEFAUT_CAPACITY)
		{
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="Stack&lt;T&gt;"/> class.
		/// </summary>
		/// <param name="capacity">The capacity.</param>
		public Stack(int capacity)
		{
			if (capacity < 0)
				throw new ArgumentOutOfRangeException("Stack size cannot be less then zero.");
			_capacity = capacity;
			_array = new T[capacity];
			_size = 0;
			_growMode = StackGrowingMode.DoubleStack;
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="Stack&lt;T&gt;"/> class.
		/// </summary>
		/// <param name="collection">The collection.</param>
		public Stack(SysGeneric.ICollection<T> collection):this()
		{
			if (collection == null)
				throw new ArgumentNullException("Supplied collection can not be null.");
			foreach(T item in collection)
				Push(item);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="Stack&lt;T&gt;"/> class.
		/// </summary>
		/// <param name="list">The list.</param>
		public Stack(SysGeneric.IList<T> list)
			: this()
		{
			if (list == null)
				throw new ArgumentNullException("Supplied collection can not be null.");
			foreach (T item in list)
				Push(item);
		}

		public Stack(T[] array) : this()
		{
			if (array == null)
				throw new ArgumentNullException("Supplied array can not be null.");
			if (array.Rank != 1)
				throw new ArgumentException("Stack cannot accept multidimention array");

			for (int index = 0; index < array.Length; index++)
				Push(array[index]);
		}
		#endregion

		#region public virtual void Push(T item)
		/// <summary>
		/// Pushes the specified item onto <see cref="Stack&lt;T&gt;"/>.
		/// </summary>
		/// <param name="item">The item to be pushed.</param>
		public virtual void Push(T item)
		{
			if (item == null)
				throw new ArgumentNullException("Item to be pushed can not be null.");
			if (_size == _array.Length)
			{
				if (FixedSize)
					throw new InvalidOperationException("Stack is full. Element can not be pushed since Stack is FixedSized");
				int growSize;
				//Calculate new size of the stack.
				if (GrowMode == StackGrowingMode.DoubleStack)
					growSize = 2 * _size;
				else
					growSize = _capacity + _size;

				T[] newArray =  new T[growSize];
				_array.CopyTo(newArray, 0);
				_array = newArray;
			}
			_array[_size++] = item;
		}
		#endregion 

		#region public virtual T Pop()
		/// <summary>
		/// Pops the top most item from the <see cref="Stack&lt;T&gt;"/>.
		/// </summary>
		/// <returns>The item poped.</returns>
		public virtual T Pop()
		{
			if (_size == 0)
				throw new InvalidOperationException("Can not perform pop when there is no item in the Stack.");
			T item = _array[--_size];
			_array[_size] = default(T);
			return item;
		}
		#endregion

		#region public virtual T Top
		/// <summary>
		/// Returns the top most element withought changing <see cref="Stack&lt;T&gt;"/>.
		/// </summary>
		/// <returns></returns>
		public virtual T Top
		{
			get
			{
				if (_size == 0)
					throw new InvalidOperationException("Can not perform pop when there is no item in the Stack.");
				return _array[_size - 1];
			}
		}
		#endregion

		#region public bool FixedSize
		private bool _fixedSize = true;
		/// <summary>
		/// Gets or sets a value indicating whether <see cref="Stack&lt;T&gt;"/> is fixed sized.
		/// </summary>
		/// <value><c>true</c> if Stack is fixed sized; otherwise, <c>false</c>.</value>
		public bool FixedSize
		{
			get { return _fixedSize; }
			set { _fixedSize = value; }
		}
		#endregion

		#region public bool IsFull
		/// <summary>
		/// Gets a value indicating whether <see cref="Stack&lt;T&gt;"/> is full.
		/// </summary>
		/// <value><c>true</c> if this instance is full; otherwise, <c>false</c>.</value>
		public bool IsFull
		{
			get 
			{
				if (FixedSize)
				{
					if (_size == _array.Length)
					{
						return true;
					}
				}
				return false;
			}
		}
		#endregion

		public bool IsEmpty
		{
			get 
			{
				return true; 
			}
		}

		#region public int Capacity
		int _capacity;
		/// <summary>
		/// Gets or sets the capacity of the <see cref="Stack&lt;T&gt;"/>.
		/// </summary>
		/// <value>The capacity.</value>
		public int Capacity
		{
			get { return _capacity; }
			set { _capacity = value; }
		}
		#endregion

		#region public GCollectionGrowingMode GrowMode
		private StackGrowingMode _growMode;
		/// <summary>
		/// Gets or sets the grow mode of the <see cref="Stack&lt;T&gt;"/>.
		/// </summary>
		/// <value>The grow mode.</value>
		public StackGrowingMode GrowMode
		{
			get { return _growMode; }
			set { _growMode = value; }
		}
		#endregion

		#region public object SyncRoot
		private static object _syncRoot;
		/// <summary>
		/// Gets the SyncRoot, an object that help to created synchronized objects.
		/// </summary>
		/// <value>The sync root.</value>
		[ComVisible(false)]
		public object SyncRoot
		{
			get 
			{
				if (_syncRoot == null)
				{
					object newRoot = new object();
					System.Threading.Interlocked.CompareExchange(ref _syncRoot, newRoot, null);
				}
				return _syncRoot;
			}
		}
		#endregion

		#region public bool IsSynchronized
		/// <summary>
		/// Gets a value indicating whether this instance is synchronized.
		/// </summary>
		/// <value>
		/// 	<c>true</c> if this instance is synchronized; otherwise, <c>false</c>.
		/// </value>
		public bool IsSynchronized
		{
			get
			{
				return false;
			}
		}
		#endregion

		/// <summary>
		/// Returns the synchronized version of <see cref="<see cref="Stack&lt;T&gt;"/>"/>.
		/// </summary>
		/// <param name="stack">The stack.</param>
		/// <returns></returns>
		public static Stack<T> Synchronized(Stack<T> stack)
		{
			return new SynchronizedStack<T>(stack) as Stack<T>;
		}


		#region ICollection<T> Members


		void SysGeneric.ICollection<T>.Add(T item)
		{
			throw new NotSupportedException("Stack class dose not support this method. Use Push method to add item on the stack.");
		}

		bool SysGeneric.ICollection<T>.Remove(T item)
		{
			throw new Exception("Stack does not support this method. Use Pop method to remove item from the stack.");
		}

		/// <summary>
		/// Removes all items from the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
		/// </summary>
		/// <exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only. </exception>
		public void Clear()
		{
			PerfomReadonlyValiadtion();
			if (_size>0)
				Array.Clear(_array, 0, _size);
            _size = 0;
		}

		/// <summary>
		/// Determines whether the <see cref="T:System.Collections.Generic.ICollection`1"></see> contains a specific value.
		/// </summary>
		/// <param name="item">The object to locate in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
		/// <returns>
		/// true if item is found in the <see cref="T:System.Collections.Generic.ICollection`1"></see>; otherwise, false.
		/// </returns>
		public virtual bool Contains(T item)
		{
			return false;
		}

		/// <summary>
		/// Copies the elements of the <see cref="T:System.Collections.Generic.ICollection`1"></see> to an <see cref="T:System.Array"></see>, starting at a particular <see cref="T:System.Array"></see> index.
		/// </summary>
		/// <param name="array">The one-dimensional <see cref="T:System.Array"></see> that is the destination of the elements copied from <see cref="T:System.Collections.Generic.ICollection`1"></see>. The <see cref="T:System.Array"></see> must have zero-based indexing.</param>
		/// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
		/// <exception cref="T:System.ArgumentOutOfRangeException">arrayIndex is less than 0 or greater than array length.</exception>
		/// <exception cref="T:System.ArgumentNullException">array is null.</exception>
		/// <exception cref="T:System.ArgumentException">array is multidimensional.-or-arrayIndex is equal to or greater than the length of array.-or-The number of elements in the source <see cref="T:System.Collections.Generic.ICollection`1"></see> is greater than the available space from arrayIndex to the end of the destination array.-or-Type T cannot be cast automatically to the type of the destination array.</exception>
		public void CopyTo(T[] array, int arrayIndex)
		{
			if (array == null)
				throw new ArgumentNullException("Supplied array can not be null.");
			if (arrayIndex < 0)
				throw new ArgumentOutOfRangeException();
			if (array.Rank != 1)
				throw new ArgumentException("Supplied array must be one dimensional");
			//TODO:	Stack.CopyTo
			Array.Copy(_array, 0, array , arrayIndex, _array.Length);

		}

		/// <summary>
		/// Gets the number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.
		/// </summary>
		/// <value></value>
		/// <returns>The number of elements contained in the <see cref="T:System.Collections.Generic.ICollection`1"></see>.</returns>
		public int Count
		{
			get
			{
				return _size;
			}
		}

		private bool _isReadOnly = false;
		/// <summary>
		/// Gets a value indicating whether the <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only.
		/// </summary>
		/// <value></value>
		/// <returns>true if the <see cref="T:System.Collections.Generic.ICollection`1"></see> is read-only; otherwise, false.</returns>
		public bool IsReadOnly
		{
			get 
			{
				return _isReadOnly;
			}
		}



		#endregion

		#region IEnumerable<T> Members

		public SysGeneric.IEnumerator<T> GetEnumerator()
		{
			for (int index = 0; index < _array.Length; index++)
				yield return _array[index];
		}

		#endregion

		#region IEnumerable Members

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return GetEnumerator() as System.Collections.IEnumerator;
		}

		#endregion

		#region ICloneable Members

		public object Clone()
		{
			return Generic.Patterns.Prototype<Stack<T>>.Clone(this);
		}

		#endregion

		#region protected void PerfomReadonlyValiadtion()
		/// <summary>
		/// Perfoms the readonly valiadtion.
		/// </summary>
		/// <exception cref="T:System.NotSupportedException"
		protected void PerfomReadonlyValiadtion()
		{
			if (IsReadOnly)
				throw new NotSupportedException("Can not change read only stack.");
		}
		#endregion

		#region internal class LinkedListDebugView
		internal class StackDebugView
		{
			Stack<T> _stack;
			public StackDebugView(Stack<T> stack)
			{
				_stack = stack;
			}

			[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
			public T[] Items
			{
				get
				{
					int count = 0;
					T[] items = new T[_stack.Count];
					for (int index = _stack.Count - 1; index >= 0; index--)
						items[count++] = _stack._array[index];
					return items;
				}
			}


			}
		#endregion

	}

	public enum StackGrowingMode
	{
		/// <summary>
		/// Grows the collection by doubling the collection size.
		/// </summary>
		DoubleStack,
		/// <summary>
		/// Grows the collection by adding <see cref="Stack<T>.Capacity"/> provide to the <see cref="T:Stack<T>"/>.
		/// </summary>
		GrowCapacity
	}


}
